BZOJ1095【ZJOI2007】Hide捉迷藏 <括号序列+线段树>

Problem

【ZJOI2007】Hide捉迷藏

Description

捉迷藏和是一对恩爱的夫妻，并且他们有很多孩子。某天，、和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由个屋子和条双向走廊组成，这条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，负责找，而负责操纵这个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：

：改变第个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
：开始一次游戏，查询最远的两个关灯房间的距离。

Input

第一行包含一个整数，表示房间的个数，房间将被编号为的整数。接下来行每行两个整数，表示房间与房间之间有一条走廊相连。接下来一行包含一个整数，表示操作次数。接着行，每行一个操作，如上文所示。

Output

对于每一个操作，输出一个非负整数，表示最远的两个关灯房间的距离。
若只有一个房间是关着灯的，输出；若所有房间的灯都开着，输出。

Sample Input

Sample Output

Hint

对于的数据，。

标签：括号序列 线段树

Solution

不会写动态点分，受小岛姐的启发写了线段树，虽然有个标记，但推出公式还是比较好写的。

括号序列
对于一棵树，我们可以将其序稍加优化，得到一个能记录每个点的子树结构的序列，即括号序列。
用左括号表示进入某点的子树，用右括号表示走出某点的子树。

对于此树，括号序列为，可以看出括号序列有一个有用的性质，即仍两点之间的序列可以表示从前面的点走到后面的点的走法。例如对于点和，其中间的序列为，如果去掉中间匹配的括号则变为，将定义为向上走，将定义为向下走，那么可以看出向上走两步，再向下走两步即可到。那么如果维护此题中的树的括号序列，那么只需要知道任意两个黑点间的括号序列消除配对后的长度的最大值后即可得到答案。

线段树维护
对于一个序列的区间，可以用二元组表示其消去配对后的序列，即有个右括号和个左括号。
对于区间和，它们合并起来的区间是，那么

当时，的左括号和的右括号消去后一定会剩下个左括号，因此，
当时，的左括号和的右括号消去后一定会剩下个右括号，因此，

那么易得到几个推论：

我们需要维护每个区间中两黑点间括号序列长度的最大值，那么我们还需要维护另外几个信息（有点像区间最大字段和）：

对于一个区间，其两个子区间的七个值分别为和，那么该区间的一定是以下四个值的最大值：

而对于维护的个信息，观察发现可以这样计算：

这样以后我们就可以用线段树维护这七个标记了。
除了有点长以外，其他都和裸线段树一样。

以后找时间把动态点分学一学吧。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
vector <int> G[MAX_N+5];
int n, cnt, col[MAX_N+5];	
int ind, seq[(MAX_N<<2)+5], dfn[MAX_N+5];
struct node {int a, b, lp, lm, rp, rm, dis;} tr[(MAX_N<<4)+5];
void addedge(int u, int v) {G[u].push_back(v), G[v].push_back(u);}
void DFS(int u, int f) {
    seq[++ind] = -1, seq[++ind] = u, dfn[u] = ind;
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if ((v = G[u][i]) ^ f) DFS(v, u);
    seq[++ind] = -2;
}
void init(int v, int p) {
    tr[v].a = tr[v].b = 0, tr[v].dis = -INF;
    if (seq[p] == -1) tr[v].b = 1;
    if (seq[p] == -2) tr[v].a = 1;
    if (seq[p] > 0 && col[seq[p]])
        tr[v].lp = tr[v].lm = tr[v].rp = tr[v].rm = 0;
    else tr[v].lp = tr[v].lm = tr[v].rp = tr[v].rm = -INF;
}
void update(int v, int s, int t) {
    int a = tr[v<<1].a, b = tr[v<<1].b;
    int c = tr[v<<1|1].a, d = tr[v<<1|1].b;
    tr[v].a = b < c ? a-b+c : a;
    tr[v].b = b < c ? d : b-c+d;
    tr[v].lp = tr[v<<1].lp, tr[v].rp = tr[v<<1|1].rp;
    tr[v].lm = tr[v<<1].lm, tr[v].rm = tr[v<<1|1].rm;
    tr[v].lp = max(tr[v].lp, tr[v<<1|1].lp+a-b);
    tr[v].lp = max(tr[v].lp, tr[v<<1|1].lm+a+b);
    tr[v].lm = max(tr[v].lm, tr[v<<1|1].lm-a+b);
    tr[v].rp = max(tr[v].rp, tr[v<<1].rp-c+d);
    tr[v].rp = max(tr[v].rp, tr[v<<1].rm+c+d);
    tr[v].rm = max(tr[v].rm, tr[v<<1].rm+c-d);
    tr[v].dis = max(tr[v<<1].dis, tr[v<<1|1].dis);
    tr[v].dis = max(tr[v].dis, tr[v<<1|1].lm+tr[v<<1].rp);
    tr[v].dis = max(tr[v].dis, tr[v<<1|1].lp+tr[v<<1].rm);
}
void build(int v, int s, int t) {
    if (s == t) {init(v, s);	return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    update(v, s, t);
}
void modify(int v, int s, int t, int p) {
    if (s == t) {init(v, s);	return;}
    if (p <= mid) modify(v<<1, s, mid, p);
    else modify(v<<1|1, mid+1, t, p);
    update(v, s, t);
}
int main() {
    read(n), cnt = n;
    for (int i = 1; i <= n; i++) col[i] = 1;
    for (int i = 1, u, v; i < n; i++)
        read(u), read(v), addedge(u, v);
    int T;	read(T), DFS(1, 0), build(1, 1, ind);
    while (T--) {
        char opt[2];	scanf("%s", opt);
        if (opt[0] == 'C') {
            int x;	read(x);
            cnt += col[x] ? -1 : 1, col[x] ^= 1;
            modify(1, 1, ind, dfn[x]);
        }
        if (opt[0] == 'G') {
            if (!cnt) puts("-1");
            else if (cnt == 1) puts("0");
            else printf("%d\n", tr[1].dis);
        }
    }
    return 0;
}